package previous.Test_0303;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
public class Solution {
    //按摩师
    //状态表示dp[i],表示总预约时间最长
    //状态转移表示
    //f[i]表示：选择到i为位置时，改位置必选 f[i]=g[i-1]+num[i];
    //g[i]表示：选择到i为位置时，改位置不选 ,其i-1位置，可选也可不选，不相邻就可以
    //                       i-1位置必选：g[i]=f[i-1]
     //                      i-1位置不选：g[i]=g[i-1]
    //                       取最大时长
    public int massage(int[] nums) {
          int n=nums.length;
          //如果没有预约时间
        if(n==0){
            return 0;
        }
          int[] dp=new int[n+1];
          int[] f=new int[n];
          int[] g=new int[n];
          f[0]=nums[0];
          g[0]=0;
          int i=0;
        for (i = 1; i < n; i++) {
            f[i]=g[i-1]+nums[i];
            g[i]=Math.max(f[i-1],g[i-1] );
        }
        return Math.max(f[i],g[i]);
    }
    //打家劫舍
    //题目概括：首位两个不能一起偷，也就是要分情况讨论
    //当偷第一个，只能偷dp[0,n-2];
    //偷第二个，只能偷dp[1,n-1];
    //分偷和不偷
    //f[i] 表示在i位置偷的最大金额：f[i]=g[i-1]+nums[i];
    //g[i] 表示在i位置不偷的最大金额：
    //     前一个位置可能偷也可以不偷
    //     i-1:偷  f[i-1]
    //     i-1:不偷 g[i-1]
    public int rob(int[] nums) {
        int n=nums.length;
        if(n==0){
            return 0;
        }
        if(n==1) return nums[0];
        int[] f=new int[n];
        int[] g=new int[n];
        int max=0;
        //偷第一个位置
        f[0]=nums[0];
        g[0]=0;
        for (int i = 1; i <n-1 ; i++) {
            f[i]=g[i-1]+nums[i];
            g[i]=Math.max(f[i-1],g[i-1]);
        }
        max=Math.max(f[n-2],g[n-2]);
        //第一个位置不偷
        f[0]=0;
        g[0]=0;
        for (int i = 1; i <n; i++) {
            f[i]=g[i-1]+nums[i];
            g[i]=Math.max(f[i-1],g[i-1]);
        }
        return Math.max(Math.max(f[n-1],g[n-1]),max);
    }
    //删除并获得点数
    public int deleteAndEarn(int[] nums) {
        //预处理
        //对数组进行排序
        //将相同数字相加
        int n=nums.length;
        int[] a=new int[10001];
        for (int i = 0; i < n; i++) {
            a[nums[i]]+=nums[i];
        }
        int[] f=new int[n];
        int[] g=new int[n];
        f[0]=a[0];
        g[0]=0;
        for (int i = 1; i < 10001; i++) {
            f[i]=g[i-1]+a[i];
            g[i]=Math.max(f[i-1],g[i-1]);
        }
        return Math.max(f[n-1],g[n-1]);
    }
}
